//
// Created by 郑楚彬 on 2018/3/27.
//
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

/**
 * 单链表结构
 */
typedef struct LNode{
    int data;
    struct LNode *next;
} LNode;

/**
 * 初始化
 * @param L
 * @return
 */
int init(LNode *&L){
    L = (LNode *) malloc(sizeof(LNode *));
    L -> next = NULL;
}

/**
 * 2. 初始化(头插法)
 *
 * @param C 链表指针
 * @param a 数组
 * @param n 长度
 */
void crateListF(LNode *&C, int a[], int n){
    LNode *s;

    C = (LNode *)malloc(sizeof(LNode *));
    C-> next = NULL;

    for(int i=0; i<n; i++){
        s = (LNode *) malloc(sizeof(LNode *));
        s->data = a[i];

        //s 所指新结点的指针域 next 指向 C 中的开始结点。
        s->next = C->next;

        //头结点的指针域 next 指向 s 结点，使得 s 成为了新的开始结点。
        C->next = s;
    }
}

/**
 * 1. 初始化(尾插法)
 *    假设有 n 个元素已经存储在数组 a 中，用尾插法建立链表 C。
 *
 * @param C 链表指针
 * @param a 数组
 * @param n 长度
 */
void createListR(LNode *&C, int a[], int n){
    //s用来指向新申请的结点，r始终指向C的终端结点。s
    LNode *s,*r;

    //申请 C 的头结点空间。
    C = (LNode *) malloc(sizeof(LNode *));
    C->next = NULL;
    r = C;

    for(int i=0; i<n; i++){
        // 指向新申请的结点
        s = (LNode *)malloc(sizeof(LNode *));
        s->data = a[i];
        // 不赋初值的话会出现 Segmentation fault
        s->next = NULL;

        //用 r 来接纳新结点。
        r->next = s;

        //r 指向终端结，点以便于接纳下一个到来的结点。
        r = r->next;
    }
    r->next = NULL;
}


/**
 * ﻿指定位置插入节点元素
 *
 * @param L
 * @param p
 * @param data
 * @return
 */
int insertLinkedList(LNode *&L, int p, int data){
    LNode *q = L, *s;
    // 当前遍历到第 i 个节点
    int i = 0;
    // 找到第 p-1 个节点
    while(q->next!=NULL && i<p-1){
        q = q->next;
        i++;
    }
    // 第 p-1 个节点为空，返回错误
    if(q == NULL){
        return 0;
    }
    // 在第 p 个节点出插入节点
    s = (LNode *) malloc(sizeof(LNode *));
    s->data = data;
    s->next = q->next;
    q->next = s;
    return 1;
}

/**
 * ﻿删除指定位置的节点
 *
 * @param L
 * @param p
 * @return
 */
int delElem(LNode *&L, int p, int &data){
    if(L->next==NULL){
        return 0;
    }
    int i=0;
    LNode *q = L, *s;

    // 找到第 p-1 个节点
    while(q->next!=NULL && i<p-1){
        q = q->next;
        i++;
    }

    // 第 p 个节点为空，返回错误
    if(q->next == NULL){
        return 0;
    }

    // 删除第 p 个节点
    s = q->next;
    q->next = s->next;
    data = s->data;
    free(s);
    return 1;
}



/**
 * (尾插法)
 * 例题 1.1  A和B是两个单链表(带表头结点)，其中元素递增有序。设计一个算法将A 和 B 归并成
 *        一个按元素递增有序的链表 C，C 由 A 和 B 中的结点组成。
 */
void mergeR(LNode *A, LNode *B, LNode *&C){
    LNode *p = A->next;
    LNode *q = B->next;
    LNode *r;

    C = (LNode*) malloc(sizeof(LNode *));
    C->next = NULL;
    r = C;

    // A、B 同时不为空时，比较数据域大小
    while(p!=NULL & q!=NULL){
        if(p->data > q->data){
            r->next = q;
            q = q->next;
        }else{
            r->next = p;
            p = p->next;
        }
        r = r->next;
    }
    r->next=NULL;

    // A不为空则将A剩余的节点拼接到C，反之亦然
    if(p != NULL)
        r->next = p;
    if(q != NULL)
        r->next = q;
}

/**
 * (头插法)
 * 例题 1.2  A和B是两个单链表(带表头结点)，其中元素递增有序。设计一个算法将A 和 B 归并成
 *        一个按元素递减有序的链表 C，C 由 A 和 B 中的结点组成。
 */
void mergeF(LNode *A, LNode*B, LNode *&C){
    LNode *p, *q;
    p = A->next;
    q = B->next;
    LNode *tmp;
    C = A;
    C->next = NULL;
    while(p!=NULL & q!=NULL){
        if(q->data > p->data){
            // printf("%d\n", p->data);
            // 头插法
            tmp = p;
            p = p->next;
            tmp->next = C->next;
            C->next = tmp;
        }else{
            // printf("%d\n", q->data);
            tmp = q;
            q = q->next;
            tmp->next = C->next;
            C->next = tmp;
        }
    }

    // 将剩余元素逐个插入 C 的头部
    while(p!=NULL){
        tmp = p;
        p = p->next;
        tmp->next = C->next;
        C->next = tmp;
    }

    while(q!=NULL){
        tmp = q;
        q = q->next;
        tmp->next = C->next;
        C->next = tmp;
    }
}

/**
 * 查找链表 C(带头结点)中是否存在一个值为 x 的结点，存在就删除之并返回 1，否则返回 0。
 *
 * ps. 程序中之所以要使 p 指向所要删除结点的前驱结点而不是直接指向所
 *     要删除结点本身，是因为要删除一个结点必须知道其前驱结点的位置
 *
 * @param C 链表指针
 * @param x 值
 * @return
 */
int SearchAndDelete(LNode *&C,int x){
    if(C==NULL){
        return 0;
    }

    // 查找部分
    LNode *p, *q;
    p = C;
    while(p->next != NULL){
        if(p->next->data == x){
            break;
        }
        p = p->next;
    }

    // 删除部分
    if(p->next == NULL){
        return 0;
    }else{
        q = p->next;
        p->next = p->next->next;
        free(q);
        return 1;
    }
}
